/*
题目：
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
解析：
看到出现次数则想到哈希表。由于大小写字符有限，因此不需使用stl中的实现，使用数组即可。
根据ASCII码，'A'-'Z',,'a'-'z'之间不连续，52个字母+6个字符共58个不同值。因此数组大小>=58即可。
使用一个数组储存每个字符出现的次数。遍历字符串，构建哈希表。由于哈希表的key值对应为数组的索引，因此不能记录每个字符出现的先后顺序。
使用一个数组储存每个字符第一次出现的位置。从后向前遍历字符串，更新每个字符出现的位置。最后数组中的位置即为第一次出现的位置。
根据以上两个哈希表，得出结果即可。
*/
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.empty())
            return -1;//预判断 str空返回-1
        int size=str.size();
        if(size==1)//预判断，str只有一个字符返回0
            return 0;
        int hash[60]={0};//'A'-'z'共52个字符，但'Z'和'a'之间有其他字符，这里>=58即可。
                         //A'-'z'出现次数
        int first[60]={-1};//'A'-'z'第一次出现位置 因为数组索引从0开始，这里为了冲突设置初值为-1
        for(int i=0;i<size;i++)
        {
            hash[str[i]-'A']++;//向后遍历str，记录'A'-'z'出现位置 'A'对应hash[0]
        }
        for(int i=size-1;i>=0;i--)
        {
            first[str[i]-'A']=i;//向前遍历str，记录'A'-'z'第一次出现位置，即在str中的相对顺序
        }
        int res=size;//令res比'A'-'z'中任何一个字符出现位置都大即可。i最大size-1，所以这里初值设为size
        for(int i=0;i<60;i++)
        {
            if(hash[i]==1)
                res=min(res,first[i]);//若某个字符只出现一次，记录其第一次出现位置，并取最小值
        }
        return res==size? -1:res;
    }
};
